#pragma once
#include "BiNode.h"
#include <queue>
#include <math.h>
struct POINT
{
	int x;
	int y;
	POINT(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
	POINT()
	{
		this->x = 0;
		this->y = 0;
	}
};

template<typename T>
class BiTree
{
public:
	BiTree(void (*input)(T &data)):root(NULL)
	{
		Create(root, input);
	}
	~BiTree(void)
	{
		Release(root);
	}
private:
	BiNode<T> *root;
	void Create(BiNode<T> * &node, void (*input)(T &data));
	void Release(BiNode<T>* node);
	void PreOrder(BiNode<T>* node, void (*visit)(T data, char split));
	void InOrder(BiNode<T>* node, void (*visit)(T data, char split));
	void PostOrder(BiNode<T>* node, void (*visit)(T data, char split));
	void LevelOrder(BiNode<T>* node, void (*visit)(T data, char split));
	int Depth(BiNode<T>* node);
	void CountLeaf(BiNode<T>* node, int &count);
	void DisplayH(BiNode<T>* node, int level, void (*visit)(T data, char split));
	void DisplayV(BiNode<T>* node , int level, void (*visit)(T data, char split));
public:
	void PreOrder(void (*visit)(T data, char split))
	{
		PreOrder(root, visit);
	}
	void InOrder(void (*visit)(T data, char split))
	{
		InOrder(root, visit);
	}
	void PostOrder(void (*visit)(T data, char split))
	{
		PostOrder(root, visit);
	}
	void LevelOrder(void (*visit)(T data, char split))
	{
		LevelOrder(root, visit);
	}
	int Depth()
	{
		return Depth(root);
	}
	int CountLeaf()
	{
		int count = 0;
		CountLeaf(root,count);
		return count;
	}
	void DisplayH(void (*visit)(T data, char split))
	{
		DisplayH(root, 0 , visit);
	}
	void DisplayV(void (*visit)(T data, char split))
	{
		DisplayV(root, 0, visit);
	}
};
template<typename T>
void BiTree<T>::Create(BiNode<T> * &node, void (*input)(T &data))
{
	T data;
	input(data);
	if (data == '#')
	{
		node = NULL;
	}
	else
	{
		node = new BiNode<T>();
		node->Data() = data;
		Create(node->LeftChild(), input);
		Create(node->RightChild(), input);
	}
	
}

template<typename T>
void BiTree<T>::Release(BiNode<T>* node)
{
	if (node)
	{
		Release(node->LeftChild());
		Release(node->RightChild());
		delete node;
		node = NULL;
	}
}

template<typename T>
void BiTree<T>::PreOrder(BiNode<T> *node, void (*visit)(T data, char split))
{
	if (!node)
	{
		return;
	}
	visit(node->Data(), ' ');
	PreOrder(node->LeftChild(), visit);
	PreOrder(node->RightChild(), visit);
}

template<typename T>
void BiTree<T>::InOrder(BiNode<T>* node, void (*visit)(T data, char split))
{
	if (!node)
	{
		return;
	}
	InOrder(node->LeftChild(), visit);
	visit(node->Data(), ' ');
	InOrder(node->RightChild(), visit);
}

template<typename T>
void BiTree<T>::PostOrder(BiNode<T>* node, void (*visit)(T data, char split))
{
	if (!node)
	{
		return;
	}
	PostOrder(node->LeftChild(), visit);
	PostOrder(node->RightChild(), visit);
	visit(node->Data(), ' ');
}

template<typename T>
void BiTree<T>::LevelOrder(BiNode<T>* node, void (*visit)(T data, char split))
{
	queue<BiNode<T>*> nodes;
	BiNode<T>* tempNode;
	if (node)
	{
		nodes.push(node);
	}
	while(!nodes.empty())
	{
		tempNode = nodes.front();
		nodes.pop();
		visit(tempNode->Data(), ' ');
		if (tempNode->LeftChild())
		{
			nodes.push(tempNode->LeftChild());
		}
		if (tempNode->RightChild())
		{
			nodes.push(tempNode->RightChild());
		}
	}
}

template<typename T>
int BiTree<T>::Depth(BiNode<T>* node)
{
	int leftLevel;
	int rightLevel;
	int levelVal;
	if (node == NULL)
	{
		levelVal = -1;
	}
	else
	{
		leftLevel = Depth(node->LeftChild());
		rightLevel = Depth(node->RightChild());
		levelVal = 1 + (leftLevel > rightLevel ? leftLevel:rightLevel); 
	}
	return levelVal;
}

template<typename T>
void BiTree<T>::CountLeaf(BiNode<T>* node, int &count)
{
	if (!node)
	{
		return;
	}
	else
	{
		if (!node->LeftChild() && !node->RightChild()) 
		{
			count++;
		}
		CountLeaf(node->LeftChild(), count);
		CountLeaf(node->RightChild(), count);
	}
}

template<typename T>
void BiTree<T>::DisplayH(BiNode<T>* node, int level, void (*visit)(T data, char split))
{
	if (!node)
	{
		return;
	}
	DisplayH(node->RightChild(), level + 1, visit);

	for (int ix = 0; ix < 2 * level; ++ix)
	{
		visit(NULL,'-');
	}
	visit(node->Data(),'\n');

	DisplayH(node->LeftChild(), level + 1, visit);
}

template<typename T>
void BiTree<T>::DisplayV(BiNode<T>* node, int level, void (*visit)(T data, char split))
{
	const unsigned int screenWidth = 64;
	const unsigned int dataWidth = 2;
	queue<BiNode<T>*> nodes;
	queue<POINT> points;
	BiNode<T>* tempNode;
	POINT tempPoint;
	POINT tempPoint2;
	int levelFlag = -1;
	int ix;
	if (node)
	{
		nodes.push(node);
		tempPoint = POINT(screenWidth / dataWidth, level);
		points.push(tempPoint);
	}
	while(!nodes.empty() && !points.empty())
	{
		tempPoint2 = tempPoint;
		tempNode = nodes.front();
		nodes.pop();
		tempPoint = points.front();
		points.pop();
		if (tempPoint.y != levelFlag)
		{
			visit(NULL, '\n');
			levelFlag = tempPoint.y;
			for (ix = 0; ix < tempPoint.x; ++ix)
			{
				visit(NULL,' ');
			}
		}
		else
		{		
			for (ix = 0; ix < tempPoint.x - tempPoint2.x; ++ix)
			{
				visit(NULL,' ');
			}
		}
		visit(tempNode->Data(), NULL);
		if (tempNode->LeftChild())
		{
			nodes.push(tempNode->LeftChild());
			points.push(POINT((int)(tempPoint.x - screenWidth / pow((double)(dataWidth), (double)(tempPoint.y + 1 + 1)) ), tempPoint.y + 1));
		}
		if (tempNode->RightChild())
		{
			nodes.push(tempNode->RightChild());
			points.push(POINT((int)(tempPoint.x + screenWidth / pow((double)(dataWidth), (double)(tempPoint.y + 1 + 1)) ), tempPoint.y + 1));
		}
	}
}